#include <iostream>
#include <vector>

// 三数取中
int medianOfThree(std::vector<int> &nums, int begin, int end)
{
    // 获取中间元素下标
    int midi = (end - begin) / 2 + begin;
#ifdef TEST
    std::cout << "三数取中--left:" << nums[begin] << "--midi:" << nums[midi] << "--right:" << nums[end] << std::endl; 
#endif
    // 让中间元素在midi下标中
    if (nums[begin] > nums[midi]) // 左端<=中间
        std::swap(nums[begin], nums[midi]);
    if (nums[begin] > nums[end]) // 左端<=右端
        std::swap(nums[begin], nums[end]);
    if (nums[midi] > nums[end]) // 中间<=右端
        std::swap(nums[midi], nums[end]);

    return midi;
}

// honor版本的单趟排序
int line_sort_honor(std::vector<int> &nums, int begin, int end)
{
    // 三数取中获取基准值下标位置
    int keyi = medianOfThree(nums, begin, end);
    // 将基准值放到最左边
    std::swap(nums[keyi], nums[begin]);

    int left = begin, right = end;
    while (left < right)
    {
        // 从右端开始找一个比基准值小的
        while (left < right && nums[begin] <= nums[right])
            right--;
        // 从左端开始找一个比基准值大的
        while (left < right && nums[begin] >= nums[left])
            left++;
        // 交换
        std::swap(nums[left], nums[right]);
    }
    // 将基准值交换到相遇位置
    std::swap(nums[begin], nums[left]);
#ifdef TEST
    std::cout << "基准值：" << nums[left] << "----";
    for (auto item : nums)
    {
        std::cout << item << " ";
    }
    std::cout << std::endl;
#endif
    // 返回相遇位置
    return left;
}

void _qsort_honor(std::vector<int> &nums, int begin, int end)
{
    if (begin >= end)
        return;

    int midi = line_sort_honor(nums, begin, end);
    // 左区间递归
    _qsort_honor(nums, begin, midi - 1);
    // 右区间递归
    _qsort_honor(nums, midi + 1, end);
}

// 快排
void qsort_honor(std::vector<int> &nums)
{
    _qsort_honor(nums, 0, nums.size() - 1);
}

int main()
{
    std::vector<int> nums = {1, 4, 5, 3, 2, 6, 4, 3, 7, 8, 6, 3, 2, 10};
    qsort_honor(nums);
    
    for (auto item : nums)
    {
        std::cout << item << " ";
    }
    std::cout << std::endl;
    return 0;
}